import java.util.Arrays;

public class Loop {
    public static void main(String[] args) {
//简易计算机
        
        int[] a = {2,9,6,3,4,7};


        //冒泡
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] < a[j+1]){
                    int b = a[j];
                    a[j] = a[j+1];
                    a[j+1] = b;
                }
            }
        }
        System.out.println("冒泡排序后：" + Arrays.toString(a));

        //选择
        for (int i = 0; i < a.length -1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]){
                    min = j;
                }
            }
            if (min != i){
                int b = a[min];
                a[min] = a[i];
                a[i] = b;
            }
        }
        System.out.println("选择排序后：" + Arrays.toString(a));

        //插入排序
        for (int i = 1; i < a.length; i++) {
            int j = i ;
            int king = a[j];
            for ( ; j > 0 && king < a[j-1]; j--) {
                a[j] = a[j-1];
            }
            a[j] = king;
        }
        System.out.println("插入排序后：" + Arrays.toString(a));

        //希尔排序
        //增量gap，并逐步缩小增量
        for (int gap = a.length / 2; gap > 0; gap /= 2) { // gap /=2 缩小增量
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i < a.length; i++) {
                int j = i;
                int pork = a[j];
                //假设： gap和0下标比较，如果0下标的值比增量gap下标的值小，则交换
                if (a[j] < a[j - gap]) {
                    while (j - gap >= 0 && pork < a[j - gap]) {
                        //移动法,让下标为0和下标为gap处的数交换位置
                        a[j] = a[j - gap];
                        j -= gap;
                    }
                    a[j] = pork;
                }
            }
        }
    }
}

